package leetcode.problems;

import java.util.Arrays;

/**
 * Created by Administrator on 2018/3/14.
 */
public class _0314NumMatchingSubseq {
  /* Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.
    Example :
    Input:
    S = "abcde"
    words = ["a", "bb", "acd", "ace"]
    Output: 3
    Explanation: There are three words in words that are a subsequence of S: "a", "acd", "ace".
    Note:

    All words in words and S will only consists of lowercase letters.
    The length of S will be in the range of [1, 50000].
    The length of words will be in the range of [1, 5000].
    The length of words[i] will be in the range of [1, 50].*/



   /*   给定字符串和字典数组，找出字典数组中字符串的子序列。
        例如:
            输入：
            S = "abcde"
            words = ["a", "bb", "acd", "ace"]
            输出：3
            说明：字典数组中有三个是s的子序列:"a", "acd", "ace"
            注：
            单词数组包含所有字母和S只包含小写字母。
            s的长度将在[ 1, 50000 ]的范围内。
            字典数组的每个子序列将在[ 1, 5000 ]的范围内。
            字典数组的长度[ i ]将在[ 1, 50 ]的范围内。*/


    public int numMatchingSubseq(String S, String[] words) {
        int n=S.length();
        int[][] next= new int[n+1][26];
        char[] sc= S.toCharArray();

        Arrays.fill(next[n], -1);
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<26;j++){
                next[i][j]=next[i+1][j];
            }
            next[i][sc[i]-'a']=i+1;
        }
        int res=0;
        for(int i=0;i<words.length;i++){
            if(isSubseq(next,words[i])) res++;
        }
        return res;

    }

    public boolean isSubseq(int[][] next,String s){
        char[] sc= s.toCharArray();
        int j=0;
        for(int i=0;i<sc.length;i++){
            char c= sc[i];
            if(next[j][c-'a']>-1) j=next[j][c-'a'];
            else return false;
        }
        return true;
    }
}
